class Solution {
public:
    int mySqrt(int x) {
        // 找最大的ans，满足ans^2<=x
        return (int)realSqrt(x);
    }

// 实数二分模板
// ans = realSqrt(x)
// 如果要求4位小数，就多算2~4位，到1e-6或1e-8，保证精确
double realSqrt(double x, double eps = 1e-6) {
    double left = 0, right = max(x, 1.0);
    while (right - left > eps) {
        double mid = (left + right) / 2;
        if (mid * mid <= x) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return right;
}
};